package dataStructure;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

import utils.Bitwise;

public class Graph<N, B> implements Serializable {
	private static final long serialVersionUID = 3021942768407351175L;

	protected Array2D<B> matrix = new Array2D<B>(0, 0);
	protected HashMap<N, Integer> map = new HashMap<N, Integer>();

	private final B NO_CONNECTION = null;

	public Graph() {}

	// SET

	public void connect(int from, int to, B branch) {
		matrix.set(to, from, branch);
	}

	public void connect(N from, N to, B branch) {
		connect(map.get(from), map.get(to), branch);
	}

	public void disconnect(int from, int to) {
		matrix.set(to, from, NO_CONNECTION);
	}

	public void disconnect(N from, N to) {
		disconnect(map.get(from), map.get(to));
	}

	public void disconnect(B b) {
		matrix.set(b, NO_CONNECTION);
	}

	public boolean contains(N node) {
		return map.containsKey(node);
	}

	public void addNode(N node) {
		matrix.addRow();
		matrix.addColumn();
		map.put(node, nNodes());
	}

	public void removeNode(N node) {
		int n = map.remove(node);
		matrix.removeRow(n);
		matrix.removeColumn(n);
		for (Entry<N, Integer> e : map.entrySet())
			if (e.getValue() > n)
				e.setValue(e.getValue() - 1);
	}

	// GET

	public B getConnection(int from, int to) {
		try {
			return matrix.get(to, from);
		} catch (Exception ex) {}
		return NO_CONNECTION;
	}

	public B getConnection(N from, N to) {
		try {
			return getConnection(map.get(from), map.get(to));
		} catch (Exception ex) {}
		return NO_CONNECTION;
	}

	public boolean isConnected(int from, int to) {
		return getConnection(from, to) != NO_CONNECTION;
	}

	public boolean isConnected(N from, N to) {
		return getConnection(from, to) != NO_CONNECTION;
	}

	public Set<N> nodes() {
		return map.keySet();
	}

	public int nNodes() {
		return map.size();
	}

	public ArrayList<B> getConnections(N Node) {
		return matrix.getRow(map.get(Node));
	}

	public ArrayList<B> getConnections(int Node) {
		return matrix.getRow(Node);
	}

	public int getNodeHash(N node) {
		return map.get(node);
	}

	public String toString() {
		return matrix.toString();
	}

	// PATH

	public Path<N> createPath(int start) {
		return new G_Path(start);
	}

	public class G_Path extends Path<N> implements Serializable {
		private static final long serialVersionUID = -4307543095179780229L;
		
		private long visited;
		private ArrayList<Integer> path;
		private int start, end;
		private String name;

		public G_Path(int start) {
			visited = 1 << start;
			path = new ArrayList<Integer>();
			this.end = this.start = start;
		}

		// get

		public int start() {
			return start;
		}

		public int end() {
			return end;
		}

		public ArrayList<Integer> path() {
			return path;
		}

		public long visited() {
			return visited;
		}

		public boolean isVisited(int node) {
			return ((1 << node) & visited) != 0;
		}

		// path expanding

		public Path<N> moveTo(int to) {
			G_Path out = new G_Path(start);
			out.visited = visited | (1 << to);
			out.path = new ArrayList<Integer>(path);
			out.path.add(to);
			out.end = to;
			return out;
		}

		public Path<N> adjust() {
			G_Path out = new G_Path(end);
			out.path = new ArrayList<Integer>();
			out.start = out.end = end;
			int i;
			out.path.add(0, end);
			for (i = path.size() - 2; i >= 0 && path.get(i) != end; i--) {
				out.path.add(0, path.get(i));
				out.visited |= 1 << path.get(i);
			}
			return out;
		}

		// intersection

		public int nIntersections(Path<N> p) {
			return (int) Bitwise.nOnes(visited & p.visited());
		}

		public boolean intersects(Path<N> p) {
			return nIntersections(p) != 0;
		}

		public Path<N> setName(String name) {
			this.name = name;
			return this;
		}

		public String toString() {
			return name;
		}
	}
}
